/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-23 10:06:21
 * @LastEditors: lily
 * @LastEditTime: 2021-04-23 10:54:43
 */
/*
 * @lc app=leetcode.cn id=56 lang=javascript
 *
 * [56] 合并区间
 */

// @lc code=start
/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
//  思路：排序
//  先对数组进行排序，再比较区间是否重合

//  复杂度：O(nlogn) O(logn)

var merge = function (intervals) {
    let res = []
    // 按照左端升序排序
    intervals.sort((a, b) => a[0] - b[0])
    for (let i = 0; i < intervals.length; i++) {
        // 第一个数或者区间不重合的数组加入解集
        if (i < 1 || intervals[i][0] > res[res.length - 1][1]) {
            res.push(intervals[i])
        } else {
            // 与解集最后一个区间比较，更新结果
            res[res.length - 1][1] = Math.max(res[res.length - 1][1], intervals[i][1])
        }
    }
    return res
};
// @lc code=end

console.log(merge([[2, 3], [4, 5], [6, 7], [8, 9], [1, 10]]));